package leetcode.array;

import leetcode.ArrayUtil;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

/**
 * @author Cheng Jun
 * Description: 编写一个程序，通过填充空格来解决数独问题。
 * <p>
 * 数独的解法需 遵循如下规则：
 * <p>
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sudoku-solver
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/12/24 22:25
 */
public class solveSudoku {

    public static void main(String[] args) {
        char[][] board = ArrayUtil.getCharTwoArr("[[\"5\",\"3\",\".\",\".\",\"7\",\".\",\".\",\".\",\".\"]," +
                "[\"6\",\".\",\".\",\"1\",\"9\",\"5\",\".\",\".\",\".\"]," +
                "[\".\",\"9\",\"8\",\".\",\".\",\".\",\".\",\"6\",\".\"]," +
                "[\"8\",\".\",\".\",\".\",\"6\",\".\",\".\",\".\",\"3\"]," +
                "[\"4\",\".\",\".\",\"8\",\".\",\"3\",\".\",\".\",\"1\"]," +
                "[\"7\",\".\",\".\",\".\",\"2\",\".\",\".\",\".\",\"6\"]," +
                "[\".\",\"6\",\".\",\".\",\".\",\".\",\"2\",\"8\",\".\"]," +
                "[\".\",\".\",\".\",\"4\",\"1\",\"9\",\".\",\".\",\"5\"]," +
                "[\".\",\".\",\".\",\".\",\"8\",\".\",\".\",\"7\",\"9\"]]");
        solveSudoku(board);
    }

    //[["5","3",".",".","7",".",".",".","."],
    // ["6",".",".","1","9","5",".",".","."],
    // [".","9","8",".",".",".",".","6","."],
    // ["8",".",".",".","6",".",".",".","3"],
    // ["4",".",".","8",".","3",".",".","1"],
    // ["7",".",".",".","2",".",".",".","6"],
    // [".","6",".",".",".",".","2","8","."],
    // [".",".",".","4","1","9",".",".","5"],
    // [".",".",".",".","8",".",".","7","9"]]
    // 这是一道典型的回溯题。一条路往前走，能进则进，不能进则退回来，换一条路再试
    static public void solveSudoku(char[][] board) {
        backTrack(board, 0, 0);
        System.out.println(board);
    }

    /**
     * row，col 表示遍历的位置
     *
     * @param board
     * @param row
     * @param col
     * @return boolean
     * @author Cheng Jun
     * @date 2021/12/24 23:33
     * 编程感悟：复杂的回溯，应该从最简单的开始考虑，比如这题，可以先思考 board是一个只有 board[0][0] 没有填的有效数独
     * <p>
     * 我们可以考虑按照「行优先」的顺序依次枚举每一个空白格中填的数字，通过递归 + 回溯的方法枚举所有可能的填法。
     * 当递归到最后一个空白格后，如果仍然没有冲突，说明我们找到了答案；
     * 在递归的过程中，如果当前的空白格不能填下任何一个数字，那么就进行回溯。
     * <p>
     * 链接：https://leetcode-cn.com/problems/sudoku-solver/solution/jie-shu-du-by-leetcode-solution/
     */
    // 是否找到答案标识
    static boolean flag = false;
    static void backTrack(char[][] board, int row, int col) {
        // row 等于9 表示已经遍历完表格
        if (row == 9) {
            flag = true;
            return;
        }
        // 空格处理逻辑
        if (board[row][col] == '.') {
            // 获取所有可以选择的数字
            LinkedList<Character> options = new LinkedList<>(getOptions(board, row, col));
            // 可选项不为空集合，并且还没找到答案 就要往下找，
            // 如果找到答案了，就不用管还剩的数字了，就相当于已经找到正确的路径，后面的路径肯定是错误的，就不会管了（因为条件说了答案只有一个）
            while (!options.isEmpty() && !flag) {
                // 取出一个可选数赋值给该位置，并递归
                board[row][col] = options.poll();
                backTrack(board, row + (col + 1) / 9, (col + 1) % 9);
            }
            // 如果所有的可选项 都用完了，并且还没找到答案 就要回溯。
            // 注意 可选项用完的时候，有可能找到了答案，所以不能仅根据是否用完可选项 来决定是否回溯。
            if (options.isEmpty() && !flag){
                board[row][col] = '.';
            }
        } else {
            backTrack(board, row + (col + 1) / 9, (col + 1) % 9);
        }
    }

    /**
     * 获取 该位置的 可以选择的数字
     *
     * @param board
     * @param row
     * @param col
     * @return java.util.Set<java.lang.Character>
     * @author Cheng Jun
     * @date 2021/12/25 17:23
     */
    static Set<Character> getOptions(char[][] board, int row, int col) {
        Set<Character> optionsSet = new HashSet<>();
        optionsSet.add('1');
        optionsSet.add('2');
        optionsSet.add('3');
        optionsSet.add('4');
        optionsSet.add('5');
        optionsSet.add('6');
        optionsSet.add('7');
        optionsSet.add('8');
        optionsSet.add('9');
        for (int i = 0; i < 9; i++) {
            // 该行拥有的其它数字
            if (board[row][i] != '.') optionsSet.remove(board[row][i]);
            // 该列拥有的其它数字
            if (board[i][col] != '.') optionsSet.remove(board[i][col]);
        }
        // 整数除法
        int rowStart = row / 3 * 3;
        int colStart = col / 3 * 3;
        // 3x3 格子 拥有的数字
        for (int i = rowStart; i < rowStart + 3; i++) {
            for (int j = colStart; j < colStart + 3; j++) {
                if (board[i][j] != '.') optionsSet.remove(board[i][j]);
            }
        }
        return optionsSet;
    }
}
